package cn.xkai.exercise.b;

import java.util.HashMap;
import java.util.Objects;

/**
 * @description: 复制带随机指针的链表
 * @author: kaixiang
 * @date: 2022-07-25
 **/
public class Solution95 {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head, q;
        while (p != null) {
            q = new Node(p.val);
            map.put(p, q);
            p = p.next;
        }
        p = head;
        q = map.get(p);
        while (p != null) {
            q.next = map.get(p.next);
            q.random = map.get(p.random);
            q = q.next;
            p = p.next;
        }
        return map.get(head);
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;
            Node node = (Node) o;
            return val == node.val && Objects.equals(next, node.next) && Objects.equals(random, node.random);
        }

        @Override
        public int hashCode() {
            return Objects.hash(val, next, random);
        }
    }
}
